package 动态规划.另类的;

import org.junit.Test;

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/29 19:26
 */
public class leetcode673最长递增子序列的个数 {


    /*
     其实 思路  是正确的， 但是细节的处理上面不正确！
     */

    public int solution(int[] nums){
        Map<Integer,Integer> map  = new TreeMap<>((a,b) -> a - b);
        int dp[] = new int[nums.length],max = 1;
        dp[nums.length - 1] = 1;
        map.put(1,1);
        for(int i = nums.length - 2;i >= 0;i--){
            dp[i] = 1;
            int count = 0;
            for(int j = i + 1;j < nums.length;j++){
                if(nums[i] < nums[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            max = Math.max(max,dp[i]);
//            map.put(dp[i],map.getOrDefault(dp[i],0) + 1);
//            map.put(max,map.getOrDefault(max,0) + 1);
        }

        return map.get(max);
    }
    /*
     上面的实现有点错误
     下面也是错误的， 确实 有点 coding 难度！
     */
    public int solutionUpdate(int[] nums){
        Map<Integer,Integer> map  = new TreeMap<>((a,b) -> a - b);
        int dp[] = new int[nums.length],max = 1;
        dp[nums.length - 1] = 1;
        map.put(1,1);
        for(int i = nums.length - 2;i >= 0;i--){
            dp[i] = 1;
            int count = 1;
            for(int j = i + 1;j < nums.length;j++){
                if(nums[i] < nums[j]){
                    if(dp[i] == dp[j] + 1){
                        count++;
                    }else{
                        dp[i] = Math.max(dp[i],dp[j] + 1);
                    }

                }
            }
            max = Math.max(max,dp[i]);
            map.put(dp[i],map.getOrDefault(dp[i],0) + count);
//            map.put(max,map.getOrDefault(max,0) + 1);
        }

        return map.get(max);
    }


/*
    dp[index][0] : 表示的 是 以 index 开头的 最长增序列的长度
    dp[index][1] : 表示的是 以 index 开头的 最长增 序列的 个数

    - 一定要 把我住 上面的 含义：
    很抽象的！
 */

    public static  int  function(int nums[]){
        int ans = 0,len = nums.length , dp[][] = new int[len][2], max = 1;

        dp[len - 1][0] = 1;
        dp[len - 1][1] = 1;
        for(int index = len - 2;index >= 0;index--){
            dp[index][0] = 1;
            dp[index][1] = 1;
            for(int i = index + 1;i < len;i++){
                // 下面很抽象！
                if(nums[index] < nums[i]){
                    if(dp[index][0] == dp[i][0] + 1){  // 说明  找到了 相同长度的 序列， 则 累加 个数
                        dp[index][1] += dp[i][1];
                    }else if(dp[index][0] < dp[i][0] + 1){ // 说明找到 了 长度更长的序列， 则 index 和 i 其实 整体变成一个序列， 所以 个数直接 集成 i 的  就行
                        dp[index][0] = dp[i][0] + 1;
                        dp[index][1] = dp[i][1];
                    }
                }
            }
            max = Math.max(max,dp[index][0]);
        }
        for(int num[] : dp){
            if(num[0] == max){
                ans += num[1];
            }
        }
        System.out.println(max);
        System.out.println(ans);
        return ans;
    }








    public static void main(String[] args) {
        int nums[] = {1,2,4,3,5,4,7,2};
        function(nums);
    }





}
